﻿#define  _CRT_SECURE_NO_WARNINGS
//给定一个单链表 L 的头节点 head ，单链表 L 表示为：
//
//L0 → L1 → … → Ln - 1 → Ln 
//请将其重新排列后变为：
//
//L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
//
//不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
//
//
//
//来源：力扣（LeetCode）
//链接：https ://leetcode.cn/problems/LGjMqU
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverse(struct ListNode* l2)
{
    struct ListNode* pre = NULL;
    struct ListNode* cur = l2;
    while (cur)
    {
        struct ListNode* temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;

    }
    return pre;
}

void reorderList(struct ListNode* head) {
    if (head == NULL)
    {
        return NULL;
    }

    struct ListNode* cur = head;
    int n = 0;
    while (cur)
    {
        cur = cur->next;
        n++;
    }
    n = (n - 1) / 2;
    cur = head;
    while (n)
    {
        cur = cur->next;
        n--;
    }
    struct ListNode* l2 = cur->next;//第二半链表
    l2 = reverse(l2);
    cur->next = NULL;
    struct ListNode* l1 = head;//第一半链表
    while (l1 && l2)
    {
        struct ListNode* next1 = l1->next;
        l1->next = l2;
        l1 = next1;

        struct ListNode* next2 = l2->next;
        l2->next = l1;
        l2 = next2;


    }
    return head;

}